home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / Changes next >
Text File  |  1994-11-16  |  43KB  |  1,343 lines
  1. +==============================================================================+
  2. |                                           |
  3. |                             VERSION 3.1                                      |
  4. |                                                                              |
  5. +==============================================================================+
  6.  
  7. -  libWx.a,  libWxv.a, libWsv.a, ...
  8.  
  9.  
  10. compare functions:
  11.  
  12. arguments to list<T>::sort, array<T>::sort, array<T>::binary_search , etc.
  13. must be of type int cmp(const T&, const T&)
  14.                           ^         ^
  15.                           |         |
  16.  
  17.  
  18.  
  19.  
  20. +==============================================================================+
  21. |                                           |
  22. |                             VERSION 3.0                                      |
  23. |                                                                              |
  24. +==============================================================================+
  25.  
  26. LEDA-3.0    (template version)
  27.  
  28. LEDA-N-3.0  (non-template version)
  29.  
  30.  
  31. ------------------------------------------------------------------------------
  32. TEMPLATES & PARAMETERIZED DATA TYPES   (cf. manual, section 1.1)
  33. ------------------------------------------------------------------------------
  34.   
  35. Starting with version 3.0 LEDA is using C++ templates for parameterized 
  36. data types (e.g. dictionary<string,int>). This makes declare macros 
  37. (e.g. declare2(dictionary,string,int)) and the "LEDA_TYPE_PARAMETER" macro 
  38. obsolete. Any built-in, pointer, item, or user-defined class type can be used 
  39. as actual type parameter for a parameterized data type. Class types however 
  40. have to provide the following operations:
  41.  
  42.   a constructor taking no arguments   T::T()
  43.   a copy constructor                  T::T(const T&)
  44.   a Read function                     void Read(T&, istream&)
  45.   a Print function                    void Print(const T&, ostream&)
  46.  
  47. A compare function  "int compare(const T&, const T&)" (cf. section 1.4 of the 
  48. user manual) has to be defined if required by the data type.
  49.  
  50. Currently, the template version can be used with cfront 3.0.1 and g++-2.3.1.
  51. Note however that there are still many bugs in g++-2.3 (most of them should
  52. be fixed in the next version). In particular, there are problems with function
  53. templates that still make the use of the "LEDA_TYPE_PARAMETER" macro necessary 
  54. for non-pointer type parameters.
  55.  
  56. For compilers not supporting templates there is a non-template variant "LEDA-N"
  57. available whose parameterized data types are based on declare-macros as in
  58. the previous LEDA versions.
  59.  
  60. See "prog/basic/param.c" for an example.
  61.  
  62.  
  63. ------------------------------------------------------------------------------
  64.  IMPLEMENTATION PARAMETERS         (cf. user manual, section 1.2)
  65. ------------------------------------------------------------------------------
  66.    
  67. For many of the parameterized data types (dictionary,priority queue,d_array,
  68. sortseq) there are variants taking an additional data structure parameter 
  69. for choosing a particular implementation, e.g. 
  70.  
  71. _dictionary<string,int,skiplist>  D 
  72.  
  73. creates a dictionary D with key type string and information type int 
  74. implemented by the skiplist data structure.
  75.  
  76. Any such type _XYZ<T1,...,Tk,impl> is derived from the corresponding
  77. "normal" parameterized type XYZ<T1,...,Tk>, i.e., an instance of type 
  78. _XYZ<T1,...,Tk,impl> can be passed as argument to functions with a 
  79. formal parameter of type XYZ<T1,...,Tk>&. This provides a mechanism for
  80. choosing implementations of data types in pre-compiled algorithms.
  81.  
  82. See "prog/graph/dijkstra.c" for an example.
  83.  
  84.  
  85.  
  86. Language Limitations: 
  87. --------------------
  88. Templates cannot be overloaded (why ?), so we have to use different names. 
  89. The names of data types with implementation parameters start with an 
  90. underscore:
  91.  
  92. _dictionary<K,I,impl>
  93. _priority_queue<K,I,impl>
  94. _d_array<I,E,impl>
  95. _sortseq<K,I,impl>
  96.  
  97.  
  98. Compiler Limitations: 
  99. --------------------
  100. Cfront 3.0.1 does not allow template arguments to be used as base classes.
  101. Therefore, we still have to use the macros from <generic.h> here:
  102.  
  103. declare3(_dictionary,K,I,impl)        ---->    _dictionary(K,I,impl)
  104. declare3(_priority_queue,K,I,impl)    ---->    _priority_queue(K,I,impl)
  105. declare3(_sortseq,K,I,impl)           ---->    _sortseq(K,I,impl)
  106. declare3(_d_array,I,E,impl)           ---->    _d_array(K,I,impl)
  107.  
  108.  
  109.  
  110. Example Programs:
  111. -----------------
  112. _dictionary<K,I,impl>              prog/dict/dic_test.c
  113. _priority_queue<K,I,impl>          prog/graph/dijkstra.c
  114. _sortseq<K,I,impl>                 prog/plane/seg_int.c
  115. _d_array<K,I,impl>                 prog/dict/d_array_test.c
  116.  
  117.  
  118. A data structure "impl" for a data type has to provide a certain 
  119. set of operations and to use certain virtual functions for type 
  120. dependent operations (cf. manual, section 9). 
  121.  
  122. Sample header files for implementations of dictionaries, priority_queues, 
  123. and sorted sequences can be found in <LEDA/impl/dic_impl.h>,
  124. <LEDA/impl/prio_impl.h>, <LEDA/impl/seq_impl.h>.
  125.  
  126.  
  127.  
  128. ------------------------------------------------------------------------------
  129. LINEAR ODERS
  130. ------------------------------------------------------------------------------
  131.  
  132. There is a new mechanism for deriving differently ordered type variants from
  133. a data type. 
  134.  
  135. The macro call
  136.  
  137.          DEFINE_LINEAR_ORDER(T,cmp,T1)  
  138.  
  139. introduces a new type T1 equivalent to type T with the linear order
  140. defined by the compare function "cmp".
  141.  
  142.  
  143. Examples:   prog/basic/order.c
  144.             prog/plane/order.c
  145.   
  146.  
  147.  
  148. ------------------------------------------------------------------------------
  149.  GENERAL
  150. ------------------------------------------------------------------------------
  151.  
  152. "forall_xyz_items" no longer supported, use "forall_items"  
  153.  
  154.  
  155. ------------------------------------------------------------------------------
  156. Efficiency
  157. ------------------------------------------------------------------------------
  158. The efficiency of many data types and algorithms has been improved.
  159.  
  160. In particular:
  161.  
  162. sorting  (array::sort, list::sort)
  163.  
  164. dictionaries, sets, d_arrays, sorted sequences 
  165. (now implemented by randomized search trees)
  166.  
  167.  
  168. network algorithms:
  169.  
  170. matching, minimum spanning tree  (performance improved by a start heuristic)
  171.  
  172.  
  173. Macro LEDA_CHECKING_OFF: 
  174. turns off range checking for arrays and  node/edge_arrays
  175. (has to be defined before including LEDA header files)
  176.  
  177.  
  178. ------------------------------------------------------------------------------
  179.  Graphs
  180. ------------------------------------------------------------------------------
  181.  
  182. new operations:
  183.  
  184. node G.first_node()         
  185. node G.last_node()
  186. node G.succ_node(node)
  187. node G.pred_node(node)
  188.  
  189. edge G.first_edge()
  190. edge G.last_edge()
  191. edge G.succ_edge(edge)
  192. edge G.pred_edge(edge)
  193.  
  194.  
  195. void G.make_undirected()  inserts all edges (v,w) into the adjacency list of w
  196.                           i.e. both outgoing and incoming edges are traversed
  197.                           by forall_adj_edges
  198.  
  199. void G.make_directed()    removes all incoming edges from the adjacency lists
  200.               
  201.  
  202.  
  203. void graph_edit(window& W, GRAPH<point,int>& G) 
  204.  
  205.  
  206. cmdline_graph(graph& G, int argc, char** argv)
  207.  
  208.         builds a graph according to the command line arguments 
  209.      
  210.         command line:  <prog>        ---> test_graph()
  211.                        <prog> n      ---> complete graph with n nodes
  212.                        <prog> n m    ---> random graph with n nodes and m edges
  213.                        <prog> file   ---> read graph from "file"
  214.      
  215.  
  216. --------------------------------------------------------------------------------
  217. planar_map (PLANAR_MAP)
  218. --------------------------------------------------------------------------------
  219.  
  220.  
  221. edge  P.split_edge(edge e)
  222. edge  P.split_edge(edge e, vtype x)
  223.  
  224.       splits edge e and its reversal by introducing a new node u
  225.  
  226.  
  227. node  p.new_node(face f)
  228. node  p.new_node(face f, vtype x)
  229.  
  230.       splits face f into triangles by introducing a new node u
  231.       and connecting it to all nodes of f
  232.  
  233.  
  234.  
  235. node  p.new_node(list<edge> el)
  236. node  p.new_node(list<edge> el, vtype x)
  237.  
  238.       splits face bounded by the edges in el by introducing a new node u
  239.       and connecting it to all source nodes of edges in el
  240.  
  241.  
  242.  
  243. ------------------------------------------------------------------------------
  244.  node_pq<I>
  245. ------------------------------------------------------------------------------
  246.  
  247. I    PQ.inf(node v)               returns information of node v
  248.  
  249. bool PQ.member(node v)            true if v in PQ false otherwise
  250.  
  251.  
  252. ------------------------------------------------------------------------------
  253.  STRING
  254. ------------------------------------------------------------------------------
  255.  
  256. additional constructor    
  257.  
  258. string::string(char c)        creates the one-character string "c"
  259.  
  260.  
  261.  
  262. ------------------------------------------------------------------------------
  263.  MEMORY
  264. ------------------------------------------------------------------------------
  265.  
  266. LEDA_MEMORY_WITH_CHECK
  267.  
  268. A debug version of the LEDA_MEMORY macro (cf. manual, section 7.3), gives
  269. an error message if the same pointer is deleted twice (slow!).
  270.  
  271.  
  272. ------------------------------------------------------------------------------
  273. Directory Structure
  274. ------------------------------------------------------------------------------
  275.  
  276. a) All implementation header files have been moved to a new header subdirectory
  277.    <LEDA/impl>.
  278.  
  279. b) There is a new directory "util" containing some utility programs. Currently 
  280.    it contains a ksh variant of the Lman shell script, a program for shortening 
  281.    all file names to 15 characters (required by SCO UNIX/XENIX) and some DOS 
  282.    installation batch files.
  283.  
  284.  
  285.  
  286.  
  287. +==============================================================================+
  288. |                                           |
  289. |                           VERSION 2.2.2                        |
  290. |                                                                              |
  291. +==============================================================================+
  292.  
  293. minor changes for use with g++-2.2 and some bugs fixed 
  294.  
  295.  
  296. +==============================================================================+
  297. |                                           |
  298. |                           VERSION 2.2.1                        |
  299. |                                                                              |
  300. +==============================================================================+
  301.  
  302. Some changes made for use with g++-2.1 and libg++-2.0
  303.  
  304. Some bugs fixed : 
  305.  
  306. string::operator+ 
  307. matrix::operator=
  308. matrix::triang 
  309. GRAPH::assign
  310.  ...
  311.  
  312.  
  313. +==============================================================================+
  314. |                                           |
  315. |                           VERSION 2.2.0                        |
  316. |                                                                              |
  317. +==============================================================================+
  318.  
  319.  
  320. --------------------------------------------------------------------------------
  321. Parameterized data types
  322. --------------------------------------------------------------------------------
  323.  
  324. Now, arbitrary data types (not only pointer and simple types) can be used as 
  325. type parameters. This makes data type "real" obsolete (use "double" or "float" 
  326. instead), "real" is no longer included in the header file <LEDA/basic.h> but 
  327. is still available in <LEDA/real.h>.
  328.  
  329.  
  330. Rules for type parameters:
  331. --------------------------
  332.  
  333. 1. Build-in types (char,int,long,float,double), pointer types, and LEDA 
  334.    simple types can be used as type parameters.
  335.  
  336. 2. A class type T can be used as type parameter under the following conditions:
  337.  
  338.  
  339.    a) The following operations and functions must be defined for T
  340.  
  341.       a constructor without arguments:  T::T()
  342.       an input operator:                istream& operator>>(istream&,T&)
  343.       an output operator:               ostream& operator<<(ostream&,const T&)
  344.       a compare function:               int compare(const T&, const T&)
  345.  
  346.    b) The macro call 
  347.  
  348.                       LEDA_TYPE_PARAMETER(T) 
  349.  
  350.       must appear before the first use of T as actual type parameter.
  351.  
  352.  
  353.    c) If defined, destructor and copy constructor are used for copying and 
  354.       destroying objects.
  355.  
  356.  
  357.  
  358. See "<LEDA>/prog/basic/param.c" for an example and for more informations and 
  359. implementaion details: "S. N\"aher: Parameterized data types in LEDA", in 
  360. preparation.
  361.  
  362.  
  363.  
  364. --------------------------------------------------------------------------------
  365. simple data types 
  366. --------------------------------------------------------------------------------
  367.  
  368. Data type "real" is no longer supported (it is still available in <LEDA/real.h>)
  369. All parameters of type real have been replaced by double parameters. When
  370. reading the user manual take "real" as a synonym for "double".
  371.  
  372.  
  373.  
  374. --------------------------------------------------------------------------------
  375. graph
  376. --------------------------------------------------------------------------------
  377.  
  378. read & write overloaded for streams
  379.  
  380. int  G.read(istream I)     reads compressed representation of G from I
  381.                            returns  ... (see manual)
  382.  
  383. int  G.read(string file)   reads compressed representation of G from file
  384.                            returns  ... (see manual)
  385.  
  386. void G.write(ostream O)    writes compressed representation of G to O
  387.  
  388. void G.write(string file)  writes compressed representation of G to file
  389.  
  390.  
  391.  
  392.  
  393. --------------------------------------------------------------------------------
  394. graph algorithms
  395. --------------------------------------------------------------------------------
  396.  
  397. bool PLANAR(graph& G)   
  398.  
  399.                  Planarity test: returns true iff $G$ is planar.
  400.                  If G is planar, it is transformed into a planar map by 
  401.                  rearranging the adjaceny lists
  402.                  precondition:  G is biconnected
  403.  
  404.  
  405.  
  406. int BICONNECTED_COMPONENTS(ugraph& G, edge_array(int)& compnum)
  407.  
  408.                  computes the biconnected components of the undirected graph G
  409.                  returns the number of biconnected components and in 
  410.                  edge_array(int) compnum for each edge an integer with
  411.                  compnum[x]=compnum[y] iff edge x and y belong to the same 
  412.                  biconnected component and 0 <= compnum[e]<=m-1 for all edges e
  413.  
  414.  
  415.  
  416. --------------------------------------------------------------------------------
  417. window
  418. --------------------------------------------------------------------------------
  419.  
  420.  
  421. int  W.get_button()         non-blocking mouse read operation
  422.                             returns number of button (see read_mouse)
  423.                             if a button has been pressed and 0 otherwise
  424.  
  425. void W.set_frame_label(string label)
  426.                             makes string "label" the window frame label
  427.  
  428.  
  429.  
  430. --------------------------------------------------------------------------------
  431. Memory Management:
  432. --------------------------------------------------------------------------------
  433.  
  434. Macro for making LEDA's memory managment available for user-defined data types
  435.  
  436. LEDA_MEMORY(type)     defines new & delete operators for "type" allocating and 
  437.                       deallocating memory by LEDA's internal memory manager
  438.  
  439.  
  440. Example: class 3d_point 
  441.          { 
  442.            double x,y,z;
  443.          
  444.            public: ...
  445.          
  446.            LEDA_MEMORY(3d_point)
  447.           };
  448.  
  449.  
  450.  
  451.  
  452. Two functions for returning memory allocated by the LEDA memory manager to 
  453. the system.
  454.  
  455. void memory_clear()       frees all currently not used memory blocks
  456.  
  457. void memory_kill()        frees all memory blocks regardless
  458.                           if they are still in use or not
  459.  
  460.  
  461.  
  462.  
  463. --------------------------------------------------------------------------------
  464. New header files:
  465. --------------------------------------------------------------------------------
  466.  
  467. The basic two-dimensional data types point, segment, line, circle, polygon,
  468. and the 2d algorithms can be used separately by including the corresponding 
  469. header files. The stream data types (file_istream, file_ostream, ...) are no 
  470. longer included in <LEDA/basic.h> but are still available in <LEDA/stream.h>
  471.  
  472.  
  473.  
  474. --------------------------------------------------------------------------------
  475. Libraries:
  476. --------------------------------------------------------------------------------
  477.  
  478. The window library libWx.a (-lWx) or libWs.a (-lWs) now must appear
  479. after the plane library libP.a (-lP) on the compiler/linker command line.
  480.  
  481. For example:
  482.  
  483.      CC prog.c -lP -lG -lL -lWx -lxview -lolgx -lX11 -lm
  484.  
  485. or
  486.  
  487.      CC prog.c -lP -lG -lL -lWs -lsuntools -lsunwindow -lpixrect -lm
  488.  
  489.  
  490.  
  491.  
  492.  
  493.  
  494.  
  495. +==============================================================================+
  496. |                                           |
  497. |                           VERSION 2.1.1                        |
  498. |                                                                              |
  499. +==============================================================================+
  500.  
  501.  
  502. --------------------------------------------------------------------------------
  503. vector/matrix
  504. --------------------------------------------------------------------------------
  505.  
  506. 1. Assignment (=) and  comparison (==/!=) operators now can be applied to
  507.    vectors/matrices with different dimensions.
  508.  
  509. 2. The default initialization for arrays of vectors/matrices is the
  510.    vector/matrix of dimension 0.
  511.  
  512. 3. Problems with vector/matrix type parameters fixed.
  513.  
  514.  
  515.  
  516. --------------------------------------------------------------------------------
  517. graphics
  518. --------------------------------------------------------------------------------
  519.  
  520.  
  521. graph_edit(window W, GRAPH(point,int) G, bool directed = true);
  522.  
  523.         Graph editor, edges are represented by arrows if directed = true
  524.         and by segments if directed = false
  525.         (declaration in <LEDA/graph_edit.h>)
  526.  
  527.         see example program "prog/graphics/matching.c" for details.
  528.  
  529.  
  530. --------------------------------------------------------------------------------
  531. string
  532. --------------------------------------------------------------------------------
  533.  
  534.  
  535. string(const char*, ...)               new printf/form - like constructor
  536.                                        e.g.  s = string("x = %5.2f",x);
  537.  
  538.  
  539. --------------------------------------------------------------------------------
  540. graph algorithms
  541. --------------------------------------------------------------------------------
  542.  
  543.  
  544. list(edge) MAX_CARD_MATCHING(graph G) 
  545.  
  546.                               Maximum cardinality matching for general graphs,
  547.                               implemented by Edmond's Algorithm, returns list
  548.                               of matched edges.
  549.                               (source in  "src/graph_alg/_mc_matching.c")
  550.                 
  551.                               (worst-case running time  O(n*m) )
  552.                 
  553.  
  554.  
  555.  
  556. +==============================================================================+
  557. |                                           |
  558. |                           VERSION 2.1.0                        |
  559. |                                                                              |
  560. +==============================================================================+
  561.  
  562.  
  563. --------------------------------------------------------------------------------
  564.         !!!!!!!!!!!!  CHANGES IN HEADER FILES  !!!!!!!!!!!!!!!!!!
  565. --------------------------------------------------------------------------------
  566.  
  567. I. <LEDA/graph.h> 
  568.  
  569.  
  570. Header file <LEDA/graph.h> has been split into  
  571.  
  572.  
  573. <LEDA/graph.h>            : graph, GRAPH, node_array, edge_array
  574.  
  575. <LEDA/ugraph.h>           : ugraph, UGRAPH
  576.  
  577. <LEDA/planar_map.h>       : planar_map, PLANAR_MAP
  578.  
  579. <LEDA/graph_alg.h>        : graph algorithms + predefined node/edge array types
  580.  
  581.                             node_array(int)   edge_array(int)
  582.                             node_array(edge)  edge_array(edge)
  583.                             node_array(bool)  edge_array(bool);
  584.                             node_array(real)  edge_array(real)
  585.                             node_matrix(bool)
  586.                             node_matrix(int)
  587.                             node_matrix(real)
  588.  
  589. <LEDA/node_set.h>         : node_set
  590.  
  591. <LEDA/edge_set.h>         : edge_set
  592.  
  593. <LEDA/node_partition.h>   : node_partition
  594.  
  595. <LEDA/node_pq.h>          : node_pq
  596.  
  597. --------------------------------------------------------------------------------
  598.  
  599.  
  600. II. <LEDA/plane.h> 
  601.  
  602.  
  603. Header file <LEDA/plane.h> has been split into  
  604.  
  605. <LEDA/plane.h>      : basic geometric objects (point,segment, ...) and 
  606.                       predefined types list(point), list(segment), ...
  607.  
  608. <LEDA/plane_alg.h>  : plane algorithms, predefined type GRAPH(point,point)
  609.  
  610.  
  611. --------------------------------------------------------------------------------
  612.  
  613.  
  614. --------------------------------------------------------------------------------
  615. data type "string"
  616. --------------------------------------------------------------------------------
  617.  
  618. int       s.pos (string s_1, int i ) 
  619.  
  620.                       returns the first position of s_1 in s right of  
  621.                       position i (-1 if no such position exists)  
  622.  
  623.  
  624. string    s.insert (string s_1, int i ) 
  625.  
  626.                       returns s(0,i-1) + s_1 + s(i+1,s.length())  
  627.                       Precondition:0 <= i <= s.length()-1  
  628.  
  629.  
  630. string    s.replace (string s_1, string s_2, int i=1 ) 
  631.  
  632.                       returns the string created from s by replacing  
  633.                       the i-th occurence of s_1 in s by s_2  
  634.  
  635.  
  636. string    s.replace_all (string s_1, string s_2 ) 
  637.  
  638.                       returns the string created from s by replacing  
  639.                       all occurences of s_1 in s by s_2  
  640.  
  641.  
  642. string    s.replace (int i, int j, string s_1 ) 
  643.  
  644.                       returns the string created from s by replacing  
  645.                       s(i,j) by s_1  
  646.  
  647.  
  648. string    s.replace (int i, string s_1 ) 
  649.  
  650.                       returns the string created from s by replacing  
  651.                       s[i] by s_1  
  652.  
  653.  
  654. string    s.del (string s_1, int i=1 ) 
  655.  
  656.                       returns s.replace(s_1,"",i)  
  657.  
  658.  
  659. string    s.del_all (string s_1 ) 
  660.  
  661.                       returns s.replace_all(s_1,"")  
  662.  
  663.  
  664. string    s.del (int i, int j ) 
  665.  
  666.                       returns s.replace(i,j,"")  
  667.  
  668.  
  669. string    s.del (int i ) 
  670.  
  671.                       returns s.replace(i,"")  
  672.  
  673.  
  674. void      s.read (istream I, char delim = ' ' ) 
  675.  
  676.                       reads characters from input stream I into s  
  677.                       until the first occurence of character delim  
  678.  
  679.  
  680. void      s.read (char delim = ' ' ) 
  681.  
  682.                       read(cin,delim)  
  683.  
  684.  
  685. void      s.readline (istream I ) 
  686.  
  687.                       read(I,'\n')  
  688.  
  689.  
  690. void      s.readline () 
  691.  
  692.                       readline(cin)  
  693.  
  694.  
  695.  
  696. --------------------------------------------------------------------------------
  697. matrix
  698. --------------------------------------------------------------------------------
  699.  
  700. Operations   matrix matrix::inv()                O(n^3)
  701.              vector matrix::solve(vector)        O(n^2)
  702.              double matrix::det()                O(n^2)
  703.  
  704. are now implemented by Gaussian eliminiation.
  705.  
  706.  
  707. matrix M.solve(matrix A)    solves  M*x_i = b_i simultaneously for all 
  708.                             columns b_i of A, returns matrix (x_0,...,x_n-1)
  709.                             Preconditions: a) M is quadratic 
  710.                                            b) A.dim2() = M.dim1()
  711.  
  712.  
  713. --------------------------------------------------------------------------------
  714. list
  715. --------------------------------------------------------------------------------
  716.  
  717. list_item  L[int i]        returns i-th item (nil if i<0 or i>L.length()-1)
  718.                            cost: O(i)
  719.  
  720.  
  721.  
  722. --------------------------------------------------------------------------------
  723. sortseq
  724. --------------------------------------------------------------------------------
  725.  
  726. void      S.split (seq_item it, sortseq& S_1, sortseq& S_2 ) 
  727.  
  728.                       splits S at item it into sequences S_1 and S_2  
  729.                       and makes S empty. More precisely, if  
  730.                       S = x_1,...,x_k-1,it,x_k+1,...,x_n then  
  731.                       S1 = x_1,...,x_k-1,it and S2 = x_k+1,...,x_n  
  732.                       Precondition: it is an item in S.  
  733.  
  734. sortseq&  S.conc (sortseq& S_1 ) 
  735.  
  736.                       appends S_1 to S, makes S_1 empty, and returns S.
  737.                       Precondition: S.key(S.max()) <= S_1.key(S_1.min()).  
  738.  
  739.  
  740.  
  741.  
  742.  
  743.  
  744. --------------------------------------------------------------------------------
  745. graph  G
  746. --------------------------------------------------------------------------------
  747.  
  748. void      G.sort_nodes (node_array(T) A ) 
  749.  
  750.                       the nodes of G are sorted according to the  
  751.                       entries of node_array A (cf. section 5.7)  
  752.                       Precondition: T must be linearly ordered  
  753.  
  754. void      G.sort_edges (edge_array(T) A ) 
  755.  
  756.                       the edges of G are sorted according to the  
  757.                       entries of edge_array A (cf. section 5.7)  
  758.                       Precondition: T must be linearly ordered  
  759.  
  760.  
  761.  
  762. pretty printing:
  763.  
  764. void      G.print(string s, ostream O)
  765. void      G.print(string s)
  766. void      G.print(ostream O)
  767. void      G.print()
  768.  
  769. void      G.print_node(node v, ostream O = cout)
  770. void      G.print_edge(edge e, ostream O = cout)
  771.  
  772.  
  773.  
  774.  
  775. --------------------------------------------------------------------------------
  776. GRAPH(vtype,etype)  G
  777. --------------------------------------------------------------------------------
  778.  
  779. void      G.sort_nodes () 
  780.  
  781.                       the nodes of G are sorted according to their  
  782.                       informations. Precondition: vtype is linearly  
  783.                       ordered.  
  784.  
  785. void      G.sort_edges () 
  786.  
  787.                       the edges of G are sorted according to their  
  788.                       informations. Precondition: etype is linearly  
  789.                       ordered.  
  790.  
  791. --------------------------------------------------------------------------------
  792. node/edge_array
  793. --------------------------------------------------------------------------------
  794.  
  795. Creation of a node array (edge array)::
  796.  
  797. a) ...
  798. b) ...
  799. c) ...
  800.  
  801. d) node/edge_array(E)  A(graph G, int n, E x)    array for n nodes/edges of G
  802.                                                  Precondition: n >= |V| (|E|)
  803.  
  804.  
  805.  
  806.  
  807.  
  808.  
  809.  
  810.  
  811.  
  812.  
  813. +==============================================================================+
  814. |                                           |
  815. |                           VERSION 2.0.1                       |
  816. |                                                                              |
  817. +==============================================================================+
  818.  
  819.  
  820. --------------------------------------------------------------------------------
  821. GENERAL
  822. --------------------------------------------------------------------------------
  823.  
  824. forall_items(x,...)    can be used for all kinds of items
  825.  
  826.  
  827. Read and Write functions for user defined I/O (cf. User Manual, section 1.5)
  828. must have an additional stream argument: 
  829.  
  830.                    Read(T&, istream&)
  831.  
  832.                    defines an input function for reading objects of type T 
  833.                    from an input stream.
  834.  
  835.                    Write(T&,ostream&)
  836.  
  837.                    defines an output function for printing objects of type T 
  838.                    to an output stream.
  839.  
  840. --------------------------------------------------------------------------------
  841. string (section 2.3)
  842. --------------------------------------------------------------------------------
  843.  
  844.  
  845. string  s.tail(int i)       returns the last  i characters of s
  846.  
  847. string  s.head(int i)       returns the first i characters of s
  848.  
  849.  
  850.  
  851. --------------------------------------------------------------------------------
  852. array (section 3.1)
  853. --------------------------------------------------------------------------------
  854.  
  855.  
  856. void     A.sort (int (*cmp)(E&, E&), int l, int h ) 
  857.  
  858.                       applies the sorting operation to the sub-array  
  859.                       [l..h].  
  860.  
  861. void     A.read (istream I ) 
  862.  
  863.                       reads b-a+1 objects of type E from the input  
  864.                       stream I into the array A using the overloaded  
  865.                       Read function (section 1.5)  
  866.  
  867. void     A.read () 
  868.  
  869.                       Calls A.read(cin) to read A from  
  870.                       the standard input stream cin.  
  871.  
  872. void     A.read (string s ) 
  873.  
  874.                       As above, but uses string s as a prompt.  
  875.  
  876. void     A.print (ostream O, char space = ' ' ) 
  877.  
  878.                       Prints the contents of array A to the output  
  879.                       stream O using the overload Print function  
  880.                       (section 1.5) to print each element. The elements  
  881.                       are separated by the space character space.  
  882.  
  883. void     A.print (char space = ' ' ) 
  884.  
  885.                       Calls A.print(cout, space) to print A on  
  886.                       the standard output stream cout.  
  887.  
  888. void     A.print (string s, char space = ' ' ) 
  889.  
  890.                       As above, but uses string s as a header.  
  891.  
  892.  
  893.  
  894.  
  895. --------------------------------------------------------------------------------
  896. list  (section 3.7)
  897. --------------------------------------------------------------------------------
  898.  
  899.  
  900. void     L.read (istream I, char delim = '\n' ) 
  901.  
  902.                       reads a sequence of objects of type E terminated  
  903.                       by the delimiter delim from the input stream I  
  904.                       using the overloaded Read function (section 1.5)  
  905.                       L is made a list of appropriate length and the  
  906.                       sequence is stored in L.  
  907.  
  908. void     L.read (char delim = '\n' ) 
  909.  
  910.                       Calls L.read(cin, delim) to read L from  
  911.                       the standard input stream cin.  
  912.  
  913. void     L.read (string s, char delim = '\n' ) 
  914.  
  915.                       As above, but uses string s as a prompt.  
  916.  
  917. void     L.print (ostream O, char space = ' ' ) 
  918.  
  919.                       Prints the contents of list L to the output  
  920.                       stream O using the overload Print function  
  921.                       (section 1.5) to print each element. The elements  
  922.                       are separated by the space character space.  
  923.  
  924. void     L.print (char space = ' ' ) 
  925.  
  926.                       Calls L.print(cout, space) to print L on  
  927.                       the standard output stream cout.  
  928.  
  929. void     L.print (string s, char space = ' ' ) 
  930.  
  931.                       As above, but uses string s as a header.  
  932.  
  933.  
  934.  
  935. void     L.write (string fname ) 
  936.  
  937.                       writes G to the file with name fname. The  
  938.                       overloaded functions Print(vtype,ostream)  
  939.                       and Print(etype,ostream) (cf. section 1.6)  
  940.                       are used to write the node and edge entries  
  941.                       of G respectively.  
  942.  
  943. void     L.read (string fname ) 
  944.  
  945.                       reads G from the file with name fname. The  
  946.                       overloaded functions Read(vtype,istream)  
  947.                       and Read(etype,istream) (cf. section 1.6)  
  948.                       are used to read the node and edge entries  
  949.                       of G respectively.  
  950.  
  951. --------------------------------------------------------------------------------
  952. priority_queue  (section 4.1)
  953. --------------------------------------------------------------------------------
  954.  
  955. Operation del_min has been overloaded
  956.  
  957. K    del_min()
  958.  
  959. void del_min(K& k, I& i)
  960.  
  961.                       removes an item x with minimal information
  962.                       assigns key(x) to k and inf(x) to i.
  963.  
  964.  
  965. --------------------------------------------------------------------------------
  966. sortseq  (section 4.6)
  967. --------------------------------------------------------------------------------
  968.  
  969. Operations "succ" and "pred" have been overloaded:
  970.  
  971. seq_item  S.succ(seq_item x)
  972. seq_item  S.succ(K k)
  973. seq_item  S.pred(seq_item x)
  974. seq_item  S.pred(K k)
  975.  
  976.  
  977.  
  978. NEW DATA TYPE:
  979. --------------------------------------------------------------------------------
  980. 4.7 Persistent Dictionaries (p_dictionary)
  981. --------------------------------------------------------------------------------
  982.  
  983.  
  984. 1. DEFINITION
  985.  
  986. The difference between dictionaries (cf. section~4.3) and persistent 
  987. dictionaries lies in the fact that update operations performed 
  988. on a persistent dictionary D do not change D but create and return a 
  989. new dictionary D'. For example, D.del(k) returns the dictionary D' 
  990. containing all items it of D with key(it) != k. 
  991.  
  992. An instance D of the data type p_dictionary is a set of items (type 
  993. p_dic_item). Every item in D contains a key from a linearly ordered 
  994. data type K, called the key type of D, and an information from a data 
  995. type I, called the information type  of D. The number of items in D 
  996. is called the size of D. A dictionary of size zero is called empty. 
  997. We use <k,i> to denote an item with key k and information 
  998. i (i is said to be the information associated with key k).  For each 
  999. k in K there is at most one item <k,i> in D.
  1000.  
  1001.  
  1002.  
  1003. 2. DECLARATION
  1004.  
  1005. declare2(p_dictionary,K,I)
  1006.  
  1007. introduces a new data type with name p_dictionary(K,I) consisting of all 
  1008. persistent dictionaries with key type K and information type I.
  1009. precond K is linearly ordered.
  1010.  
  1011.  
  1012.  
  1013. 3. CREATION
  1014.  
  1015. p_dictionary(K,I) D ;
  1016.  
  1017. creates an instance D of type p_dictionary(K,I) and initializes D to an 
  1018. empty persistent dictionary. 
  1019.  
  1020.  
  1021.  
  1022. 4. OPERATIONS
  1023.  
  1024. K         D.key (dic_item it ) 
  1025.  
  1026.                       returns the key of item it.  
  1027.                       Precondition: it in D.  
  1028.  
  1029. I         D.inf (dic_item it ) 
  1030.  
  1031.                       returns the information of item it.  
  1032.                       Precondition: it in D.  
  1033.  
  1034. dic_item  D.lookup (K k ) 
  1035.  
  1036.                       returns the item with key k (nil if  
  1037.                       no such item exists in D).  
  1038.  
  1039. I         D.access (K k ) 
  1040.  
  1041.                       returns the information associated with key k  
  1042.                       Precondition: there is an item with  
  1043.                       key k in D.  
  1044.  
  1045. p_dictionary(K,I) D.del (K k ) 
  1046.  
  1047.                       returns { x in D | key(x) != k }.  
  1048.  
  1049. p_dictionary(K,I) D.del_item (dic_item it ) 
  1050.  
  1051.                       returns { x in D | x != it }.  
  1052.  
  1053. p_dictionary(K,I) D.insert (K k, I i ) 
  1054.  
  1055.                       returns D.del(k) cup {<k,i>}.  
  1056.  
  1057. p_dictionary(K,I) D.change_inf (dic_item it, I i ) 
  1058.  
  1059.                       Let k = key(it), returns D.del_item(it) cup  
  1060.                       {<k,i>}. Precondition: it in D.  
  1061.  
  1062. p_dictionary(K,I) D.clear () 
  1063.  
  1064.                       returns an empty persistent dictionary.  
  1065.  
  1066. bool      D.empty () 
  1067.  
  1068.                       returns true if D is empty, false otherwise.  
  1069.  
  1070. int       D.size () 
  1071.  
  1072.                       returns the size of D.  
  1073.  
  1074.  
  1075.  
  1076. 5. ITERATION
  1077.  
  1078. forall_items(i,D) 
  1079. { ``the items of D are successively assigned to i '' }
  1080.  
  1081.  
  1082.  
  1083. 6. IMPLEMENTATION
  1084.  
  1085. Persistent Dictionaries are implemented by leaf oriented 
  1086. persistent red black trees (cf. [DSST89]).
  1087. Operations insert, lookup, del_item, del take time O(log n), key, inf, 
  1088. empty, size, change_inf and clear take time O(1). The space requirement 
  1089. is O(n). Here n is the number of all created persistent dictionaries (= number 
  1090. of all performed update operations). 
  1091.  
  1092.  
  1093. --------------------------------------------------------------------------------
  1094. GRAPH    (section 5.4)
  1095. --------------------------------------------------------------------------------
  1096.  
  1097.  
  1098. void      G.write (string fname ) 
  1099.  
  1100.                       writes G to the file with name fname. The  
  1101.                       overloaded functions Print(vtype,ostream)  
  1102.                       and Print(etype,ostream) (cf. section 1.6)  
  1103.                       are used to write the node and edge entries  
  1104.                       of G respectively.  
  1105.  
  1106. int       G.read (string fname ) 
  1107.  
  1108.                       reads G from the file with name fname. The  
  1109.                       overloaded functions Read(vtype,istream)  
  1110.                       and Read(etype,istream) (cf. section 1.6)  
  1111.                       are used to read the node and edge entries  
  1112.                       of G respectively. Returns error code
  1113.                       1  if file fname does not exist
  1114.                       2  if graph is not of type GRAPH(vtype,etype)
  1115.                       3  if file fname does not contain a graph
  1116.                       0  otherwise.
  1117.  
  1118.  
  1119.  
  1120.  
  1121. --------------------------------------------------------------------------------
  1122. PLANE  (section 6.1.6)
  1123. --------------------------------------------------------------------------------
  1124.  
  1125.  
  1126.  
  1127. Function VORONOI  (cf. section 6.1.6) has a new interface:
  1128.  
  1129.  
  1130. void VORONOI(list(point), double R, GRAPH(point,point) )
  1131.  
  1132.         VORONOI takes as input a list of points  sites and a real number 
  1133.         R. It computes a directed graph G representing the planar subdivision
  1134.         defined by the Voronoi-diagram of sites where all ``infinite" edges have
  1135.         length R. For each node v G.inf(v) is the corresponding Voronoi 
  1136.         vertex (point) and for each edge e  G.inf(e) is the site (point) 
  1137.         whose Voronoi region is bounded by e. 
  1138.  
  1139.  
  1140.  
  1141.  
  1142. --------------------------------------------------------------------------------
  1143. point_set  (section 6.3)
  1144. --------------------------------------------------------------------------------
  1145.  
  1146. list(ps_item) S.convex_hull () 
  1147.  
  1148.                       returns the list of items containing  
  1149.                       all points of the convex hull of  
  1150.                       in clockwise order.  
  1151.  
  1152.  
  1153.  
  1154.  
  1155.  
  1156.  
  1157. --------------------------------------------------------------------------------
  1158. graphic windows  (section 6.7)
  1159. --------------------------------------------------------------------------------
  1160.  
  1161. Data type gwindow no longer exists, it is replaced by data type window
  1162.  
  1163. The data type window provides an interface for the input and 
  1164. output of basic two-dimensinal geometric objects (cf. section 5.1) 
  1165. using the X11 (xview) or SunView window system.
  1166. There are two object code libraries (libWs.a, libWx.a) containing 
  1167. implementations for different environments. Application programs using data 
  1168. type window have to be linked with one of these libraries (cf. section~1.6):
  1169.  
  1170.  
  1171. a) For the SunView window system:
  1172.  
  1173.    CC prog.c -lWs -lP -lG -lL -lm  -lsuntool -lsunwindow -lpixrect
  1174.  
  1175.  
  1176. b) For the X11 (open windows) window system:
  1177.  
  1178.    CC prog.c -lWx -lP -lG -lL -lm  -lxview -lolgx -lX11 
  1179.  
  1180.  
  1181.  
  1182. --------------------------------------------------------------------------------
  1183. Creation of a graphic window
  1184. --------------------------------------------------------------------------------
  1185.  
  1186.  
  1187. a) window W(int xpix, int ypix, int xpos, int ypos);
  1188.  
  1189. b) window W(int xpix, int ypix);
  1190.  
  1191. c) window W();
  1192.  
  1193. Variant a) creates a window W of physical size xpix times ypix pixels 
  1194. with its upper left corner at position (xpos,ypos) on the screen,
  1195. variant b) places W into the upper right corner of the screen, and
  1196. variant c) creates a 850 times 850 pixel window positioned into the
  1197. upper right corner.
  1198.  
  1199. All three variants initialize the coordinates of W to x0 = 0,
  1200. x1 = 100 and y0 = 0. The init operation (see  below) can later 
  1201. be used to change the window coordinates and scaling.
  1202.  
  1203.  
  1204.  
  1205. --------------------------------------------------------------------------------
  1206. Additional operations
  1207. --------------------------------------------------------------------------------
  1208.  
  1209.  
  1210. int       W.read_panel (string h, int n, string* S ) 
  1211.  
  1212.                       displays a panel with header h and an array S[n]  
  1213.                       of n string buttons, returns the index of the selected  
  1214.                       button.  
  1215.  
  1216. int       W.read_vpanel (string h, int n, string* S ) 
  1217.  
  1218.                       read_panel with vertical button layout
  1219.  
  1220.  
  1221. int       W.read_int (string p ) 
  1222.  
  1223.                       displays a panel with prompt p for integer input,  
  1224.                       returns the input  
  1225.  
  1226.  
  1227. real      W.read_real (string p ) 
  1228.  
  1229.                       displays a panel with prompt p for real input  
  1230.                       returns the input  
  1231.  
  1232.  
  1233. string    W.read_string (string p ) 
  1234.  
  1235.                       displays a panel with prompt p for string input,  
  1236.                       returns the input  
  1237.  
  1238.  
  1239.         
  1240. string    W.read_string (string p, list(string) menu)
  1241.  
  1242.                       as above, adds an additional menu button which
  1243.                       can be used to select a string from menu.
  1244.      
  1245. string    W.read_string (string p, string label, list(string) menu)
  1246.                       as above, the menu button is labelled with label.
  1247.  
  1248.  
  1249.  
  1250.  
  1251. --------------------------------------------------------------------------------
  1252. PANELS
  1253. --------------------------------------------------------------------------------
  1254.  
  1255.  
  1256. Creation:
  1257. --------
  1258.  
  1259. panel P(string header);
  1260.  
  1261. panel P;
  1262.  
  1263.  
  1264. Operations:
  1265. ----------
  1266.  
  1267. void P.text_item(string s)
  1268.  
  1269. void P.bool_item(string label, bool& x)
  1270.  
  1271. void P.real_item(string label, real& x)
  1272.  
  1273. void P.color_item(string label, color& x)
  1274.  
  1275. void P.int_item(string label, int& x)
  1276. void P.int_item(string label, int& x, int min, int max)              // slider
  1277. void P.int_item(string label, int& x, int low, int high, int step)   // choice
  1278.  
  1279. void P.string_item(string label, string& x)
  1280. void P.string_item(string label,string& x,list(string) L)  // menu
  1281.  
  1282. void P.choice_item(string label, int& x, list(string) L)
  1283. void P.choice_item(string label, int& x, int l, string* L)
  1284. void P.choice_item(string label, int& x, string, ... )
  1285.  
  1286. void P.button(string label)
  1287.  
  1288. void P.new_button_line()
  1289. void P.new_button_line(list(string) buttons)
  1290.  
  1291.  
  1292. int  P.open()
  1293. int  P.open(list(string)& buttons)
  1294.  
  1295.  
  1296. --------------------------------------------------------------------------------
  1297. 7. Miscellaneous
  1298. --------------------------------------------------------------------------------
  1299.  
  1300. --------------------------------------------------------------------------------
  1301. Command input streams (cmd_istream)
  1302. --------------------------------------------------------------------------------
  1303.  
  1304. An instance I of the data type cmd_istream is an C++ istream
  1305. connected to the output of a shell command cmd, i.e., all input operations 
  1306. or operators applied to I read from the standard output of command cmd. 
  1307.  
  1308. 1. Creation of a command input stream 
  1309.  
  1310. cmd_istream   in(string cmd);
  1311.  
  1312. creates an instance in of type cmd_istream connected to the output of command cmd.
  1313.  
  1314. 2. Operations
  1315.  
  1316. All operations and operators (>>) defined for C++ istreams can
  1317. be applied to command input streams as well.
  1318.  
  1319.  
  1320.  
  1321.  
  1322. --------------------------------------------------------------------------------
  1323. Command output streams (cmd_ostream)
  1324. --------------------------------------------------------------------------------
  1325.  
  1326. An instance O of the data type cmd_ostream is an C++ ostream
  1327. connected to the input of a shell command cmd, i.e., all output operations 
  1328. or operators applied to O write into the standard input of command cmd. 
  1329.  
  1330. 1. Creation of a command output stream} 
  1331.  
  1332. cmd_ostream   out(string cmd);
  1333.  
  1334. creates an instance out of type cmd_ostream connected to the input of 
  1335. command cmd. 
  1336.  
  1337. 2. Operations 
  1338.  
  1339. All operations and operators (<<) defined for C++ ostreams can
  1340. be applied to command output streams as well.
  1341.  
  1342.  
  1343.